18.6 KB · ⇊ 11 parts · ⤓ Micron 18.6 KB · ⤓ HTML 93.8 KB

top

L'algorithme de Berlekamp est une méthode de factorisation des polynômes à coefficients dans un corps fini, qui repose sur des calculs de PGCD de polynômes et des opérations matricielles. Il a été découvert par Elwyn Berlekamp en 1967, et est resté l'algorithme le plus performant concernant ce problème jusqu'en 1981, et la découverte de l'algorithme de Cantor-Zassenhaus.

• Description

• Un exemple

• Première étape : Mise sous forme unitaire sans facteur carré

• Deuxième étape : Calcul de la matrice

• Troisième étape : Calcul du noyau

• Quatrième étape : Factorisation

• Complexité de l’algorithme

• Applications

• Références

L'algorithme exige de travailler sur un polynôme unitaire f(x) sans facteur carré, c'est-à-dire que les exposants des facteurs dans la décomposition en irréductibles de f valent tous 1. On note n son degré et q le nombre d'éléments du corps fini Fq sur lequel on se place.

Le point central est la recherche et l'utilisation de polynômes g tels que gq – g soit divisible par f. Dans l'anneau quotient Fq[x]/(f(x)), les images de ces polynômes forment une sous-Fq-algèbre, dite « algèbre de Berlekamp ». Tout élément du quotient Fq[x]/(f(x)) s'identifie à un polynôme g de degré strictement inférieur à n et g est dans l'algèbre de Berlekamp si et seulement si

∏

∏

s

∈

∈

F

q

p

g

c

d

(

f

(

x

)

,

g

(

x

)

−

−

s

)

=

f

(

x

)

.

{\displaystyle \prod _{s\in \mathbb {F} _{q}}{\rm {pgcd}}(f(x),g(x)-s)=f(x).}

Démonstration

On remarque d'abord que les polynômes g(x) – s sont deux à deux premiers entre eux donc, en notant P(x) leur produit :

∏ ∏ s ∈ ∈ F q p g c d ( f ( x ) , g ( x ) − − s ) = p g c d ( f ( x ) , P ( x ) ) . {\displaystyle \prod _{s\in \mathbb {F} _{q}}{\rm {pgcd}}(f(x),g(x)-s)={\rm {pgcd}}(f(x),P(x)).}

Or P(x) est égal à M(g(x)) avec

M ( y ) := ∏ ∏ s ∈ ∈ F q ( y − − s ) = y q − − y , {\displaystyle M(y):=\prod _{s\in \mathbb {F} _{q}}(y-s)=y^{q}-y,}

la dernière égalité étant due au fait que ces deux polynômes sont unitaires, de degré q et nuls sur Fq.

Le polynôme P est donc égal à gq – g. Par conséquent, pgcd(f, P) = f si et seulement si f divise gq – g, c'est-à-dire si g est dans l'algèbre de Berlekamp.

Si de plus g est non « trivial » (c'est-à-dire non constant), aucun des facteurs pgcd(f, g – s) n'est égal à f donc au moins un facteur est distinct de f et de 1. On a ainsi décomposé le polynôme f en produit de polynômes unitaires, dont l'un est distinct de f et de 1 : on a factorisé f. Pour obtenir une factorisation en produit de polynômes irréductibles, il suffit d'appliquer cette méthode récursivement.

Pour trouver des polynômes g non triviaux dans l'algèbre de Berlekamp, on part du constat que la puissance q-ième d'un polynôme g(x) = g0 + g1x + … + gn–1xn–1, à coefficients dans Fq, s'écrit g(x)q = g0 + g1xq + … + gn–1xq(n–1) (cf. Endomorphisme de Frobenius). En notant ainsi la réduction modulo f des monômes xiq :

x i q ≡ ≡ ∑ ∑ j = 0 n − − 1 α α i , j x j mod f ( x ) , {\displaystyle x^{iq}\equiv \sum _{j=0}^{n-1}\alpha _{i,j}x^{j}\mod \;f(x),}

on obtient alors :

g ( x ) q ≡ ≡ ∑ ∑ j = 0 n − − 1 ( ∑ ∑ i g i α α i , j ) x j mod f ( x ) . {\displaystyle g(x)^{q}\equiv \sum _{j=0}^{n-1}(\sum _{i}g_{i}\alpha _{i,j})x^{j}\mod \;f(x).}

Les monômes xj, pour j = 0, … , n – 1, forment une Fq-base de l'espace vectoriel Fq[x]/(f(x)) ; on obtient donc, par identification des coefficients, que g est un élément de l'algèbre de Berlekamp si et seulement si l'identité matricielle suivante est vérifiée :

( g 0 … … g n − − 1 ) ( α α 0 , 0 … … α α 0 , n − − 1 ⋮ ⋮ ⋮ ⋮ α α n − − 1 , 0 … … α α n − − 1 , n − − 1 ) = ( g 0 … … g n − − 1 ) . {\displaystyle {\begin{pmatrix}g_{0}&\ldots &g_{n-1}\end{pmatrix}}{\begin{pmatrix}\alpha _{0,0}&\dots &\alpha _{0,n-1}\\\vdots &&\vdots \\\alpha _{n-1,0}&\dots &\alpha _{n-1,n-1}\end{pmatrix}}={\begin{pmatrix}g_{0}&\ldots &g_{n-1}\end{pmatrix}}.}

L'algorithme consiste donc à calculer la matrice A des αi,j puis à tenter, par la méthode du pivot de Gauss, de trouver un vecteur ligne (g0 … gn–1) tel que (g0 … gn–1)(A – In) = 0, où In désigne la matrice identité (ou si l'on préfère : un vecteur colonne du noyau de l'application représentée par la matrice transposée, At – In) ; si on en trouve un non trivial alors on peut factoriser f par des calculs de pgcd, via l'algorithme d'Euclide. Enfin, on montre que s'il n'existe pas d'élément non trivial dans l'algèbre de Berlekamp, alors le polynôme f est irréductible. Plus précisément : la dimension de cette algèbre est égale au nombre de facteurs irréductibles de f.

Démonstration

Soient f1, … , fk les polynômes unitaires irréductibles distincts dont f est le produit. Par le théorème des restes chinois, on a un isomorphisme de Fq-algèbres :

F

q

[

x

]

/

(

f

)

≃

≃

F

q

[

x

]

/

(

f

1

)

⊕

⊕

…

…

⊕

⊕

F

q

[

x

]

/

(

f

k

)

.

{\displaystyle \mathbb {F} _{q}[x]/(f)\simeq \mathbb {F} _{q}[x]/(f_{1})\oplus \ldots \oplus \mathbb {F} _{q}[x]/(f_{k}).}

Tout polynôme g ayant ses k composantes constantes dans cette décomposition est bien sûr dans l'algèbre de Berlekamp mais aussi, réciproquement, si g est dans l'algèbre, l'identité

g

q

−

−

g

=

∏

∏

s

∈

∈

F

q

(

g

−

−

s

)

{\displaystyle g^{q}-g=\prod _{s\in \mathbb {F} _{q}}(g-s)}

(déjà justifiée et utilisée dans la démonstration précédente) montre que chaque fi divise l'un des g – s. Le cardinal de cette algèbre est par conséquent qk donc sa dimension sur Fq est k.

On applique l'algorithme au polynôme Q = 2 X 3 + 2 X + 1 {\displaystyle Q=2X^{3}+2X+1} , que l'on va factoriser dans F 3 {\displaystyle \mathbb {F} _{3}} .

On pose P ( X ) = 2 2 Q ( X 2 ) {\displaystyle P(X)=2^{2}Q({\dfrac {X}{2}})} . Ainsi, P = X 3 + X + 1 m o d 3 {\displaystyle P=X^{3}+X+1~mod~3} , qui est bien unitaire. Pour se ramener à un polynôme sans facteur carré, on divise par p g c d ( P , P ′ ) {\displaystyle pgcd(P,P')} . Ici, P {\displaystyle P} est déjà sans facteur carré. Une fois décomposé P {\displaystyle P} , on remonte à la décomposition de Q {\displaystyle Q} comme suit : si P = F G {\displaystyle P=FG} , on a Q ( X ) = P ( 2 X ) 2 2 = F ( 2 X ) G ( 2 X ) 2 2 {\displaystyle Q(X)={\dfrac {P(2X)}{2^{2}}}={\dfrac {F(2X)G(2X)}{2^{2}}}} , ce qui donne une factorisation de Q {\displaystyle Q} .

Pour calculer la matrice de l’application M : a ↦ ↦ a 3 − − a {\displaystyle M~:~a\mapsto a^{3}-a} , on calcule l’image des vecteurs de base de l’algèbre de Berlekamp, soit 1 , X , X 2 {\displaystyle 1,X,X^{2}} . On va donc être amené à calculer X 3 {\displaystyle X^{3}} et X 6 {\displaystyle X^{6}} modulo P {\displaystyle P} . On a :

X 3 = − − X − − 1 {\displaystyle X^{3}=-X-1}

X 4 = − − X 2 − − X {\displaystyle X^{4}=-X^{2}-X}

X 5 = − − X 2 + X + 1 {\displaystyle X^{5}=-X^{2}+X+1}

X 6 = X 2 − − X + 1 {\displaystyle X^{6}=X^{2}-X+1}

La matrice de M {\displaystyle M} dans la base canonique est donc : ( 0 − − 1 1 0 1 − − 1 0 0 0 ) {\displaystyle \left({\begin{array}{c c c}0&-1&1\\0&1&-1\\0&0&0\\\end{array}}\right)}

Le polynôme g = X 2 + X {\displaystyle g=X^{2}+X} , non constant, est dans le noyau de cette matrice.

P = p g c d ( ( X 2 + X ) , P ) ∗ ∗ p g c d ( ( X 2 + X − − 1 ) , P ) ∗ ∗ p g c d ( ( X 2 + X + 1 ) , P ) = ( X − − 1 ) ( X 2 + X − − 1 ) {\displaystyle P=pgcd((X^{2}+X),P)*pgcd((X^{2}+X-1),P)*pgcd((X^{2}+X+1),P)=(X-1)(X^{2}+X-1)}

Or cette décomposition est composée de facteurs irréductibles (on peut s’en assurer en appliquant l’algorithme à chaque facteur). Donc Q = ( 2 X 2 + X + 1 ) ( X + 1 ) {\displaystyle Q=(2X^{2}+X+1)(X+1)} .

La recherche d’un facteur non constant d’un polynôme P de degré n dans F q {\displaystyle \mathbb {F} _{q}} est en O ( q n 3 ) {\displaystyle O(qn^{3})} .

Démonstration

Rappelons d’abord que pour deux polynômes P et Q, la complexité de la division euclidienne de P par Q est de l’ordre de O ( d e g ( q ) ( d e g ( p ) − − d e g ( q ) + 1 ) ) {\displaystyle O(deg(q)(deg(p)-deg(q)+1))} et celle du pgcd est en O ( d e g ( p ) d e g ( q ) ) {\displaystyle O(deg(p)deg(q))} .

La première étape de l’algorithme est donc en O ( n 2 ) {\displaystyle O(n^{2})} .

Ensuite, le calcul de la matrice consiste alors à faire n {\displaystyle n} divisions euclidiennes de polynômes, dont le degré est majoré par n q {\displaystyle nq} , par P. Cette étape est alors en O ( n ( n ( n q − − n + 1 ) ) ) = O ( q n 3 ) {\displaystyle O(n(n(nq-n+1)))=O(qn^{3})} La résolution du système de taille n 2 {\displaystyle n^{2}} se fait par pivot de Gauss et a donc une complexité en O ( n 3 ) {\displaystyle O(n^{3})} .

Enfin, il ne reste plus qu’à calculer au pire n {\displaystyle n} pgcd de degré au plus n {\displaystyle n} , ce qui s’effectue en O ( n 3 ) {\displaystyle O(n^{3})} . Finalement, on a le résultat voulu.

Une application importante de l’algorithme de Berlekamp réside dans le calcul informatique de logarithmes discrets sur les corps finis F p n {\displaystyle \mathbb {F} _{p}^{n}} où p {\displaystyle p} est un nombre premier et n {\displaystyle n} un nombre entier naturel supérieur ou égal à 2. Le calcul de logarithmes discrets est une problématique importante pour la cryptographie asymétrique et les codes correcteurs. Pour un corps fini, la méthode la plus rapide est l'algorithme de calcul d'indice (en), qui inclut la factorisation des éléments du corps. Si l'on représente le corps F p n {\displaystyle \mathbb {F} _{p}^{n}} de manière courante - c’est-à-dire, en tant que polynômes du corps F p {\displaystyle \mathbb {F} _{p}} , réduits modulo un polynôme irréductible de degré n {\displaystyle n} - alors, il s’agit d’une simple factorisation polynomiale, telle qu’obtenue avec l’algorithme de Berlekamp.

D'autre part, l'algorithme de Berlekamp constitue la première étape de la factorisation de polynômes à coefficients entiers (donc aussi pour des coefficients rationnels), qui utilise aussi le lemme de Hensel et l'algorithme LLL. En effet, intuitivement, en choisissant un q {\displaystyle q} suffisamment grand, les opérations ne seront pas réduites modulo q ce qui permettra d'avoir la factorisation attendue. Une borne minimale pour un tel q {\displaystyle q} peut être obtenu grâce aux bornes de Landau-Mignotte.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Berlekamp's algorithm » (voir la liste des auteurs).

• berlekamp1967e-r-berlekamp1967(en) E. R. Berlekamp, « Factoring Polynomials Over Finite Fields », Bell Syst. Tech. J., vol. 46, no 8,‎ 1967, p. 1853-1859 (DOI 10.1002/j.1538-7305.1967.tb03174.x)

• demazuremichel-demazureMichel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions]

• knuth1981donald-knuth1981(en) Donald Knuth, The art of computer programming/Seminumerical Algorithms, t. 2, Addison Wesley, 1981 (ISBN 0-201-03822-6), p. 421-425

• lidlniederreiter1994rudolf-lidlharald-niederreiter1994(en) Rudolf Lidl et Harald Niederreiter, Introduction to Finite Fields and Their Applications, CUP, 1994, 416 p. (ISBN 978-0-521-46094-1, présentation en ligne), p. 133-141

• abuaf-roland-et-boyer-ivan2007Abuaf Roland et Boyer Ivan, « Factorisation dans Z [ X ] {\displaystyle \mathbb {Z} [X]} », Sujet de maîtrise proposé par François Loeser,‎ 2007 (lire en ligne)

• Portail de l’algèbre

• Portail de l'informatique théorique